package com.leetcode.partition15;

import java.io.*;
import java.util.*;

/**
 * @author `RKC`
 * @date 2022/2/1 14:56
 */
public class LC1489找到最小生成树里的关键边和伪关键边_枚举 {

    private static final int N = 110;
    private static int n = 0, m = 0, cnt = 0;
    private static int[] parent = new int[N];
    private static int[][] edges, indices = new int[N][N];

    private static final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        String[] ss = reader.readLine().split(" ");
        int n = Integer.parseInt(ss[0]), m = Integer.parseInt(ss[1]);
        int[][] edges = new int[m][3];
        for (int i = 0; i < m; i++) {
            ss = reader.readLine().split(" ");
            int a = Integer.parseInt(ss[0]), b = Integer.parseInt(ss[1]), c = Integer.parseInt(ss[2]);
            edges[i] = new int[]{a, b, c};
        }
        List<List<Integer>> answer = findCriticalAndPseudoCriticalEdges(n, edges);
        for (List<Integer> ans : answer) writer.write(ans + "\n");
        writer.flush();
    }

    public static List<List<Integer>> findCriticalAndPseudoCriticalEdges(int _n, int[][] _edges) {
        List<List<Integer>> answer = new ArrayList<>();
        for (int i = 0; i < 2; i++) answer.add(new ArrayList<>());
        n = _n;
        edges = _edges;
        //题目没有重边，根据两个端点找到唯一的边在原数组中的索引，映射边在原数组中的位置
        for (int i = 0; i < _edges.length; i++) {
            int a = _edges[i][0], b = _edges[i][1], c = _edges[i][2];
            indices[a][b] = i;
        }
        m = _edges.length;
        Arrays.sort(edges, 0, m, (o1, o2) -> Integer.compare(o1[2], o2[2]));
        //先得到最小生成树的权值和
        for (int i = 0; i < N; i++) parent[i] = i;
        int sum = kruskal(-1);
        //枚举每一条边，将该条边删除后得到的MST权值和与sum比较，判断是否是关键边
        for (int i = 0; i < m; i++) {
            int a = edges[i][0], b = edges[i][1], c = edges[i][2];
            for (int j = 0; j < N; j++) parent[j] = j;
            int val = kruskal(i);
            //如果删除了当前边导致不能得到MST或者权值增大，说明是一条关键边。否则判断如果加入这条边后得到的MST是否等于sum
            if (cnt != 1 || val > sum) {
                answer.get(0).add(indices[a][b]);
            } else {
                for (int j = 0; j < N; j++) parent[j] = j;
                //提前加入该边，做kruskal算法
                parent[a] = b;
                val = c + kruskal(-1);
                if (val == sum) answer.get(1).add(indices[a][b]);
            }
        }
        return answer;
    }

    private static int kruskal(int del) {
        cnt = n;
        int res = 0;
        for (int i = 0; i < m; i++) {
            if (i == del) continue;
            int a = edges[i][0], b = edges[i][1], c = edges[i][2];
            int x = find(a), y = find(b);
            if (x != y) {
                cnt--;
                parent[x] = y;
                res += c;
            }
        }
        return res;
    }

    private static int find(int x) {
        if (x == parent[x]) return x;
        return parent[x] = find(parent[x]);
    }
}
